package Hard;
//23.合并K个升序链表
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode p = null ;
        ListNode res = null;
        if(lists.length==0) return null;
        if(lists.length==1) return lists[0];
        //非空元素个数
        int count = 0;
        ListNode[] dev0lists = new ListNode[lists.length];
        //去掉空的元素
        for(int i = 0,j=0 ; i < lists.length ; i++){
            if(lists[i]!=null){
                dev0lists[j++]=lists[i];
                count++;
            }
        }
        if(count==1)
            return dev0lists[0];
        boolean first = true;
        //现在将dev0lists里的所有升序链表进行合并
        //每次循环找出一个最小数
        while (true){
            int minIndex = -1;
            int min = 10000;//由题可知，没有比10000更大的数
            int i;
            for(i = 0 ; i < count ; i++){
                if(dev0lists[i]!=null && dev0lists[i].val < min){
                    min=dev0lists[i].val;
                    minIndex=i;
                }
            }
            if(minIndex==-1){
                //结束循环
                break;
            }
            if(first){
                p=dev0lists[minIndex];
                res=p;
            }
            else {
                p.next=dev0lists[minIndex];
                p=p.next;
            }
            first=false;

            dev0lists[minIndex]=dev0lists[minIndex].next;

        }
        return res;
    }
}



class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}